package tree.maxpath;

public class MaxPath {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        int i = maxPath(root);
        System.out.println(i);
    }
        public static int maxPath(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = maxPath(root.left);
        int right = maxPath(root.right);
        if(left == 0 && right == 0){
            return root.val;
        }
        if(left == 0){
            return right;
        }
        if(right == 0){
            return left;
        }
        return Math.max(left,right) + root.val;
    }
}
